package com.example.learn.hwod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class _203二叉树的还原和求和 {

    static class TreeNode {
        int num;
        int childSum;
        TreeNode left;
        TreeNode right;

        public TreeNode(int num) {
            this.num = num;
            this.childSum = 0;
            this.left = null;
            this.right = null;
        }
    }

    static int[] midOrder;
    static int[] preOrder;
    static HashMap<Integer, ArrayList<Integer>> midIndexMap = new HashMap<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        midOrder = Arrays.stream(sc.nextLine().split("")).mapToInt(Integer::parseInt).toArray();
        preOrder = Arrays.stream(sc.nextLine().split("")).mapToInt(Integer::parseInt).toArray();

        int n = midOrder.length;
        for (int i = 0; i < n; i++) {
            int num = midOrder[i];
            midIndexMap.putIfAbsent(num, new ArrayList<>());
            midIndexMap.get(num).add(i);

        }

        // 根据中序序列和前序序列还原树结构
        TreeNode root = buildTree(0, n - 1, 0, n - 1);

    }

    public static TreeNode buildTree(int midL, int midR, int preL, int preR) {
        if (preL > preR) {
            return null;
        }
        int rootNum = preOrder[preL];
        TreeNode root = new TreeNode(rootNum);
        for (Integer index : midIndexMap.get(rootNum)) {
            if (index < midL || index > midR) {
                continue;
            }
            int leftLen = index - midL;
            if (notEquals(midL, preL + 1, leftLen)) continue;
            // 如果中序的右子树，和前序的右子树不同，则对应根值位置不正确
            int rightLen = midR - index;
            if (notEquals(index + 1, preR - rightLen + 1, rightLen)) continue;
            // 找到正确根值位置后，开始分治递归处理左子树和右子树
            root.left = buildTree(midL, index - 1, preL + 1, preL + leftLen);
            root.right = buildTree(index + 1, midR, preR - rightLen + 1, preR);

            // 记录该节点：左子树+右子树的和（本题新二叉树节点的值）
            root.childSum =
                    (root.left == null ? 0 : (root.left.num + root.left.childSum))
                            + (root.right == null ? 0 : (root.right.num + root.right.childSum));

            break;

        }
        return null;
    }

    public static boolean notEquals(int midL, int preL, int size) {
        int[] arr1 = Arrays.stream(Arrays.copyOfRange(midOrder, midL, midL + size)).sorted().toArray();
        int[] arr2 = Arrays.stream(Arrays.copyOfRange(preOrder, preL, preL + size)).sorted().toArray();

        for (int i = 0; i < size; i++) {
            if (arr1[i] != arr2[i]) {
                return true;
            }
        }

        return false;

    }
}